// Author: Ivan Kazmenko (gassa@mail.ru)
// Generator for problem "triangle"
module gen;
import std.algorithm;
import std.conv;
import std.exception;
import std.format;
import std.math;
import std.random;
import std.range;
import std.stdio;

immutable string testFormat = "%03d";
enum generateAnswers = false;

immutable int minN =   1;
immutable int maxN = 100;
immutable int maxC = 100;

struct Point
{
	int x;
	int y;

	bool isValid () const
	{
		return abs (x) <= maxC && abs (y) <= maxC;
	}

	string toString () const
	{
		return format ("%s %s", x, y);
	}
}

int vp () (const auto ref Point a,
    const auto ref Point b, const auto ref Point c)
{
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int dist2 () (const auto ref Point a, const auto ref Point b)
{
	return (a.x - b.x) ^^ 2 + (a.y - b.y) ^^ 2;
}

struct TestCase
{
	Point a, b, c;
	Point p, q;

	void validate () const
	{
		foreach (z; only (a, b, c, p, q))
		{
			enforce (z.isValid ());
		}

		foreach (z; only (a, b, c))
		{
			enforce (z.x < 0);
		}
		enforce (vp (a, b, c) != 0);

		foreach (z; only (p, q))
		{
			enforce (z.x > 0);
		}
		enforce (p != q);
	}
}

struct Test
{
	TestCase [] cases;

	string comment;

	@property auto n () const
	{
		return cases.length;
	}

	void validate () const
	{
		enforce (minN <= n && n <= maxN);
		foreach (ref tc; cases)
		{
			tc.validate ();
		}
	}

	void print (File f) const
	{
		f.writeln (n);
		foreach (ref tc; cases)
		{
			f.writefln ("%(%s  %)",
			    only (tc.a, tc.b, tc.c, tc.p, tc.q));
		}
	}

	string log () const
	{
		return format ("%s (%s cases)", comment, n);
	}
}

Test [] tests;

void printAllTests ()
{
	foreach (testNumber, test; tests)
	{
		test.validate ();
		auto testString = format (testFormat, testNumber + 1);
		auto f = File (testString, "wt");
		test.print (f);
		static if (generateAnswers)
		{
			auto g = File (testString ~ ".a", "wt");
			test.printAnswer (g);
		}
		writeln (testString, ": ", test.log ());
	}
}

Mt19937 rndLocal;
T rndValue (T) () {return uniform !(T) (rndLocal);}
T rndValue (T) (T lim) {return uniform (cast (T) (0), lim, rndLocal);}
T rndValue (T) (T lo, T hi) {return uniform (lo, hi, rndLocal);}
auto rndChoice (R) (R r) {return r[rndValue (cast (int) (r.length))];}

void rndShuffle (R) (R r)
{
	auto len = r.length.to !(int);
	foreach (i; 0..len)
	{
		int k = rndValue (i, len);
		r.swapAt (i, k);
	}
}

TestCase [] shuffleTriangles (TestCase [] cases)
{
	foreach (ref tc; cases)
	{
		if (rndValue (2))
		{
			swap (tc.a, tc.b);
		}
		if (rndValue (2))
		{
			swap (tc.b, tc.c);
		}
		if (rndValue (2))
		{
			swap (tc.a, tc.b);
		}
	} 
	return cases;
}

TestCase [] genEqual (int n, int lo, int hi)
{
	TestCase [] res;
	foreach (i; 0..n)
	{
		Point p;
		Point q;
		do
		{
			p.x = rndValue (1, hi);
			p.y = rndValue (1, hi);
			q.x = rndValue (1, hi);
			q.y = rndValue (1, hi);
		}
		while (p.x == q.x || p.y == q.y || dist2 (p, q) < lo ^^ 2);

		Point [] s;
		foreach (dx; [-1, +1])
		{
			foreach (dy; [-1, +1])
			{
				s ~= Point (-50 + p.x * dx, +50 + p.y * dy);
			}
		}
		rndShuffle (s);
		res ~= TestCase (s[0], s[1], s[2], p, q);
	}
	return res;
}

TestCase [] shake (TestCase [] cases, int delta)
{
	foreach (ref tc; cases)
	{
		tc.a.x += rndValue (-delta, delta + 1);
		tc.a.y += rndValue (-delta, delta + 1);
		tc.b.x += rndValue (-delta, delta + 1);
		tc.b.y += rndValue (-delta, delta + 1);
		tc.c.x += rndValue (-delta, delta + 1);
		tc.c.y += rndValue (-delta, delta + 1);
		tc.p.x += rndValue (-delta, delta + 1);
		tc.p.y += rndValue (-delta, delta + 1);
		tc.q.x += rndValue (-delta, delta + 1);
		tc.q.y += rndValue (-delta, delta + 1);
	} 
	return cases;
}

TestCase [] genRandom (int n, int lo, int hi)
{
	TestCase [] res;
	foreach (i; 0..n)
	{
		Point p;
		Point q;
		do
		{
			p.x = rndValue (1, 101);
			p.y = rndValue (-100, 101);
			q.x = rndValue (1, 101);
			q.y = rndValue (-100, 101);
		}
		while (dist2 (p, q) < lo ^^ 2 || dist2 (p, q) > hi ^^ 2);

		Point a;
		Point b;
		Point c;
		do
		{
			a.x = rndValue (-100, 0);
			a.y = rndValue (-100, 101);
			b.x = rndValue (-100, 0);
			b.y = rndValue (-100, 101);
			c.x = rndValue (-100, 0);
			c.y = rndValue (-100, 101);
		}
		while (vp (a, b, c) == 0 || dist2 (a, b) < lo ^^ 2 ||
		     dist2 (b, c) < lo ^^ 2 || dist2 (a, c) < lo ^^ 2);

		res ~= TestCase (a, b, c, p, q);
	}
	return res;
}

TestCase [] genInteresting (int n, int lo, int hi)
{
	TestCase [] res;
	while (res.length < n)
	{
		Point p;
		Point q;
		do
		{
			p.x = rndValue (1, 101);
			p.y = rndValue (-100, 101);
			q.x = rndValue (1, 101);
			q.y = rndValue (-100, 101);
		}
		while (dist2 (p, q) < lo ^^ 2 || dist2 (p, q) > hi ^^ 2);

		Point a;
		Point b;
		Point c;
		do
		{
			a.x = rndValue (-100, 0);
			a.y = rndValue (-100, 101);
			b.x = rndValue (-100, 0);
			b.y = rndValue (-100, 101);
			c.x = rndValue (-100, 0);
			c.y = rndValue (-100, 101);
		}
		while (a.x == c.x || a.y == c.y ||
		     b.x == c.x || b.y == c.y || c.x == a.x || c.y == a.y ||
		     vp (a, b, c) == 0 || dist2 (a, b) < lo ^^ 2 ||
		     dist2 (b, c) < lo ^^ 2 || dist2 (a, c) < lo ^^ 2);

		long area2 = vp (a, b, c) ^^ 2;
		long base2 = max (dist2 (a, b), dist2 (b, c), dist2 (c, a));
		long gate2 = dist2 (p, q);
		if (area2 != gate2 * base2)
		{
			continue;
		}

		res ~= TestCase (a, b, c, p, q);
	}
	return res;
}

void main ()
{
	rndLocal.seed (157_159_005);

	tests ~= Test ([
	    TestCase (Point (  -1,   0), Point (  -2,   0), Point (  -2,   3),
	    Point (  1,   1), Point (  1,   2)),
	    ], "example test 1");

	tests ~= Test ([
	    TestCase (Point (  -1,   0), Point (  -2,   0), Point (  -2,   3),
	    Point (  1,   0), Point (  3,   0)),
	    TestCase (Point (  -1,   0), Point (  -5,   7), Point (  -9,  -1),
	    Point (  3,   4), Point (  6,   8)),
	    ], "example test 2");

	tests ~= Test ([
	    TestCase (Point ( -10,   0), Point ( -20,   0), Point ( -15,   5),
	    Point ( 10,   0), Point ( 13,  14)),
	    TestCase (Point (  -6,   3), Point ( -13,   4), Point ( -14,  -3),
	    Point (  1,   0), Point (  6,   0)),
	    TestCase (Point (-100,   0), Point ( -60,  40), Point ( -50, -30),
	    Point (  2,   0), Point (  1,   0)),
	    TestCase (Point (  -6,   3), Point ( -17,   1), Point ( -14,  -3),
	    Point (  6,   0), Point (  1,   0)),
	    ], "small test");

	tests ~= Test ([
	    TestCase (Point ( -10,   0), Point ( -11,   0), Point ( -10,  -1),
	    Point (  1,   0), Point (  2,   0)),
	    TestCase (Point ( -10,   0), Point ( -11,   0), Point ( -10,  -1),
	    Point (  1,   0), Point (  2,   1)),
	    TestCase (Point ( -10,   0), Point ( -11,   0), Point ( -10,  -1),
	    Point (  1,   0), Point (  3,   0)),
	    TestCase (Point ( -10,   0), Point ( -11,   1), Point ( -12,   0),
	    Point (  1,   0), Point (  2,   0)),
	    TestCase (Point ( -10,   0), Point ( -11,   1), Point ( -12,   0),
	    Point (  1,   0), Point (  2,   1)),
	    TestCase (Point ( -10,   0), Point ( -11,   1), Point ( -12,   0),
	    Point (  1,   0), Point (  3,   0)),
	    TestCase (Point ( -10,   0), Point ( -11,   2), Point ( -12,   0),
	    Point (  1,   0), Point (  2,   0)),
	    TestCase (Point ( -10,   0), Point ( -11,   2), Point ( -12,   0),
	    Point (  1,   0), Point (  2,   1)),
	    TestCase (Point ( -10,   0), Point ( -11,   2), Point ( -12,   0),
	    Point (  1,   0), Point (  3,   0)),
	    TestCase (Point ( -10,   0), Point ( -11,   2), Point ( -12,   1),
	    Point (  1,   0), Point (  3,   0)),
	    ], "minimum test");

	tests ~= Test ([
	    TestCase (Point (-100,   0), Point ( -1, -100), Point (  -1, 100),
	    Point (  1, 100), Point (  1,  99)),
	    TestCase (Point (-100,   0), Point ( -1, -100), Point (  -1, 100),
	    Point (  1, 100), Point ( 1, -100)),
	    TestCase (Point (-100,   0), Point ( -1, -100), Point (  -1, 100),
	    Point (  1, 100), Point (  1,  -2)),
	    TestCase (Point (-100,   0), Point ( -1, -100), Point (  -1, 100),
	    Point (  1, 100), Point (  1,  10)),
	    TestCase (Point (-100,   0), Point ( -1, -100), Point (  -1, 100),
	    Point (  1, 100), Point (  1,  -1)),
	    TestCase (Point (-100,   0), Point ( -1, -100), Point (  -1, 100),
	    Point (  1, 100), Point (  1,   2)),
	    TestCase (Point (-100,   0), Point ( -1, -100), Point (  -1, 100),
	    Point (  1, 100), Point (  1,   1)),
	    TestCase (Point (-100,   0), Point ( -1, -100), Point (  -1, 100),
	    Point (  1, 100), Point (  1,   0)),
	    TestCase (Point (-100,   0), Point ( -1, -100), Point (  -1, 100),
	    Point (  1, 100), Point (  1, -10)),
	    ], "maximum test");

	tests ~= Test ([
	    TestCase (Point (  -1,   0), Point (-35,   55), Point ( -56,  89),
	    Point ( 1, -100), Point ( 1,  -99)),
	    TestCase (Point (  -1,   0), Point (-22,   34), Point ( -35,  55),
	    Point ( 1,   99), Point ( 1,  100)),
	    TestCase (Point (  -1,   0), Point (-14,   21), Point ( -22,  34),
	    Point ( 1,  100), Point ( 1,   99)),
	    TestCase (Point (  -1,   0), Point ( -9,   13), Point ( -14,  21),
	    Point ( 1,   99), Point ( 1,  100)),
	    TestCase (Point (  -1,   0), Point ( -6,    8), Point (  -9,  13),
	    Point (100,   1), Point (99,    1)),
	    TestCase (Point (  -1,   0), Point ( -4,    5), Point (  -6,   8),
	    Point ( 1,  100), Point ( 1,   99)),
	    TestCase (Point (  -1,   0), Point ( -3,    3), Point (  -4,   5),
	    Point ( 1,  -99), Point ( 1, -100)),
	    TestCase (Point (  -1,   0), Point ( -2,    2), Point (  -3,   3),
	    Point ( 1,  -99), Point ( 1, -100)),
	    TestCase (Point (  -1,   0), Point ( -2,    1), Point (  -2,   2),
	    Point (99,    1), Point (100,   1)),
	    TestCase (Point (  -1,   0), Point ( -1,    1), Point (  -2,   1),
	    Point ( 1, -100), Point ( 1,  -99)),
	    ].shuffleTriangles, "Fibonacci test");

	tests ~= Test ([
	    TestCase (Point (-100,  23), Point ( -1,  100), Point ( -1,  -40),
	    Point ( 1,  100), Point ( 1,   64)),
	    ] ~ genEqual (9, 1, 50), "precision test");

	tests ~= Test (genEqual (10, 10, 44).shake (1), "shaked test");

	foreach (nt; 1..4)
	{
		tests ~= Test (genRandom (10, 1 + nt * 10, 11 + nt * 20),
		    format ("random test %s", nt));
	}

	tests ~= Test (genInteresting (10, 1, 250), "interesting test");

	printAllTests ();
}
